🧠 C/C++'ta Baştan Sona Hash Table (Karma Tablo) Uygulaması

Bu rehberde, C/C++ dillerinde sıfırdan bir Karma Tablo (Hash Table) oluşturmayı öğreneceksiniz.
Kendi hash fonksiyonunuzu, bağlı liste (linked list) tabanlı çakışma çözümünüzü ve bellek yönetimi sisteminizi inşa edeceğiz.
Sonunda ise performanslı, dinamik ve bellek güvenli bir hash table elde edeceksiniz.

---

🎯 Bu Rehberde Ne Öğreneceksiniz?

• Hash (Karma) fonksiyonunun nasıl yazıldığını
• Key–Value (Anahtar–Değer) yapısının oluşturulmasını
• Çakışmaların (Collision) Separate Chaining ile nasıl çözüldüğünü
• Bellek tahsisi ve serbest bırakma yöntemlerini (malloc, free)
• Ekleme (insert), arama (search) ve silme (delete) fonksiyonlarının uygulanmasını

---

⚙️ 1. Hash Fonksiyonunu Tanımlama

Hash fonksiyonu, bir anahtarı tablo boyutuna uygun bir indekse dönüştürür.

#define CAPACITY 50000 // Hash tablonun maksimum boyutu

unsigned long hash_function(char* str) {
    unsigned long i = 0;
    for (int j = 0; str[j]; j++)
        i += str[j];
    return i % CAPACITY;
}

💡 Not:

Bu basit fonksiyon, karakterlerin ASCII değerlerini toplar. "Hel" ve "Cau" gibi farklı kelimeler aynı değeri üretebilir. Bu durum çakışma (collision) olarak adlandırılır.

---

🧱 2. Temel Yapıları Tanımlama

🔸 Hash Öğesi (Ht_item)

Her öğe bir key:value çifti tutar:

typedef struct Ht_item {
    char* key;
    char* value;
} Ht_item;

🔸 Hash Tablosu (HashTable)

Ana tablo, öğeleri tutan bir dizi ve olası çakışmaları yöneten “overflow bucket” dizilerini içerir:

typedef struct HashTable {
    Ht_item** items;
    struct LinkedList** overflow_buckets;
    int size;
    int count;
} HashTable;

---

💾 3. Bellek Yönetimi Fonksiyonları

🔹 Yeni bir öğe oluşturma

Ht_item* create_item(char* key, char* value) {
    Ht_item* item = (Ht_item*) malloc(sizeof(Ht_item));
    item->key = (char*) malloc(strlen(key) + 1);
    item->value = (char*) malloc(strlen(value) + 1);
    strcpy(item->key, key);
    strcpy(item->value, value);
    return item;
}

🔹 Yeni tablo oluşturma

HashTable* create_table(int size) {
    HashTable* table = (HashTable*) malloc(sizeof(HashTable));
    table->size = size;
    table->count = 0;
    table->items = (Ht_item**) calloc(size, sizeof(Ht_item*));

    for (int i = 0; i < size; i++)
        table->items[i] = NULL;

    table->overflow_buckets = (struct LinkedList**) calloc(size, sizeof(struct LinkedList*));
    return table;
}

🔹 Belleği serbest bırakma

void free_item(Ht_item* item) {
    free(item->key);
    free(item->value);
    free(item);
}

void free_table(HashTable* table) {
    for (int i = 0; i < table->size; i++)
        if (table->items[i] != NULL)
            free_item(table->items[i]);
    free(table->overflow_buckets);
    free(table->items);
    free(table);
}

---

🔗 4. Çakışma Yönetimi (Separate Chaining)

Çakışma (collision) durumunda, aynı indekse düşen elemanlar bağlı liste (linked list) şeklinde zincirlenir.

typedef struct LinkedList {
    Ht_item* item;
    struct LinkedList* next;
} LinkedList;

Bağlı listeye yeni öğe ekleme:

LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) {
    if (!list) {
        LinkedList* head = (LinkedList*) malloc(sizeof(LinkedList));
        head->item = item;
        head->next = NULL;
        return head;
    }
    LinkedList* temp = list;
    while (temp->next) temp = temp->next;
    temp->next = (LinkedList*) malloc(sizeof(LinkedList));
    temp->next->item = item;
    temp->next->next = NULL;
    return list;
}

---

➕ 5. Ekleme İşlemi (ht_insert)

void ht_insert(HashTable* table, char* key, char* value) {
    Ht_item* item = create_item(key, value);
    int index = hash_function(key);
    Ht_item* current_item = table->items[index];

    if (current_item == NULL) {
        table->items[index] = item;
        table->count++;
    } else if (strcmp(current_item->key, key) == 0) {
        strcpy(current_item->value, value);
    } else {
        table->overflow_buckets[index] = linkedlist_insert(table->overflow_buckets[index], item);
    }
}

---

🔍 6. Arama İşlemi (ht_search)

char* ht_search(HashTable* table, char* key) {
    int index = hash_function(key);
    Ht_item* item = table->items[index];
    if (item && strcmp(item->key, key) == 0)
        return item->value;

    LinkedList* head = table->overflow_buckets[index];
    while (head) {
        if (strcmp(head->item->key, key) == 0)
            return head->item->value;
        head = head->next;
    }
    return NULL;
}

---

❌ 7. Silme İşlemi (ht_delete)

void ht_delete(HashTable* table, char* key) {
    int index = hash_function(key);
    Ht_item* item = table->items[index];
    if (!item) return;

    if (strcmp(item->key, key) == 0) {
        free_item(item);
        table->items[index] = NULL;
        table->count--;
        return;
    }

    LinkedList* head = table->overflow_buckets[index];
    LinkedList* prev = NULL;
    while (head) {
        if (strcmp(head->item->key, key) == 0) {
            if (prev) prev->next = head->next;
            free_item(head->item);
            free(head);
            return;
        }
        prev = head;
        head = head->next;
    }
}

---

🧪 8. Tüm Fonksiyonların Test Edilmesi

int main() {
    HashTable* ht = create_table(CAPACITY);

    ht_insert(ht, "1", "Adres Bir");
    ht_insert(ht, "2", "Adres Iki");
    ht_insert(ht, "Hel", "Istanbul");
    ht_insert(ht, "Cau", "Ankara"); // Çakışma örneği

    printf("Hel: %s\n", ht_search(ht, "Hel"));
    printf("Cau: %s\n", ht_search(ht, "Cau"));

    ht_delete(ht, "1");
    ht_delete(ht, "Cau");

    free_table(ht);
    return 0;
}

🧠 Çıktı:

Hel: Istanbul
Cau: Ankara

---

⚖️ Hash Table – Özet Tablo

Özellik	Açıklama
Erişim Süresi	Ortalama O(1), çakışma durumunda O(n)
Çakışma Yönetimi	Separate Chaining (Linked List) yöntemi
Bellek Yönetimi	Manuel (malloc, free)
Avantaj	Hızlı erişim, düşük arama süresi
Dezavantaj	Fazladan bellek kullanımı ve uygulama karmaşıklığı

---

❓ Sıkça Sorulan Sorular (SSS)

1️⃣ Hash Table neden bu kadar hızlı?

Hash fonksiyonu doğrudan bellekteki doğru dizine erişir. Bu da ortalama O(1) erişim sağlar.

2️⃣ Çakışma (Collision) neden olur?

İki farklı anahtar aynı hash sonucunu üretirse çakışma meydana gelir. Bunun nedeni hash fonksiyonunun dağılım kalitesidir.

3️⃣ Separate Chaining dışında alternatif var mı?

Evet. Linear Probing, Quadratic Probing ve Double Hashing gibi yöntemler kullanılabilir.

4️⃣ STL’de bu yapının hazır karşılığı var mı?

Evet, std::unordered_map bu işlemleri dahili olarak yönetir ve genellikle Separate Chaining kullanır.

5️⃣ Bellek sızıntısı nasıl önlenir?

Her malloc() çağrısının bir free() karşılığı olmalı. Bu kod örneğinde hepsi manuel yönetiliyor.

---

🚀 Sonuç

Bu rehberde, C/C++’ta sıfırdan bir Hash Table (Karma Tablo) oluşturmayı, çakışmaları yönetmeyi ve dinamik bellekle güvenli çalışmayı öğrendiniz. Artık kendi hash tablonuzu kurabilir, std::unordered_map’in perde arkasını daha iyi anlayabilirsiniz.

⚡ Şimdi kendi kodunuzu test edin! Rabisu Bulut Platformu’nda sanal bir sunucu açarak, bu yapıyı gerçek zamanlı olarak deneyebilirsiniz.